package practice_2025_7_16;

import java.util.*;

public class Solution {

    /**
     * 二叉树的锯齿形遍历
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new LinkedList<>();
        boolean flg = false;
        if (root == null) return res;
        queue.add(root);
        while(!queue.isEmpty()) {
            int n = queue.size();
            List<Integer> tmp = new LinkedList<>();
            while(n-- > 0) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            if (flg) {
                Collections.reverse(tmp);
                flg = false;
            } else {
                flg = true;
            }
            res.add(tmp);
        }
        return res;
    }

    /**
     * 二叉树的最大宽度
     * 存储: 节点 + 下标，从而计算每一层的宽度
     * @param root
     * @return
     */
    public int widthOfBinaryTree(TreeNode root) {
        int max = 0;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        if (root == null) return 0;
        queue.add(new Pair<>(root, 1));
        while(!queue.isEmpty()) {
            int n = queue.size();
            int left = queue.peek().getValue();
            int right = 0;
            while(n > 0) {
                if (n == 1) {
                    right = queue.peek().getValue();
                }
                Pair<TreeNode, Integer> pair = queue.poll();
                TreeNode node = pair.getKey();
                int index = pair.getValue();
                if (node.left != null) {
                    queue.add(new Pair<TreeNode, Integer>(node.left, index * 2));
                }
                if (node.right != null) {
                    queue.add(new Pair<TreeNode, Integer>(node.right, 2 * index + 1));
                }
                //   System.out.println("n: " + n);
                n--;
            }
            // System.out.println("left: " + left + " right: " + right);
            max = Math.max(max, right - left + 1);
        }
        return max;
    }

    /**
     * 在每个数行中找最大值
     * @param root
     * @return
     */
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return res;
        queue.add(root);
        while(!queue.isEmpty()) {
            int n = queue.size();
            int max = Integer.MIN_VALUE;
            while(n-- > 0) {
                TreeNode node = queue.poll();
                max = Math.max(max, node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(max);
        }
        return res;
    }

    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        List<Integer> list = new ArrayList<>();
        Collections.reverse(list);
        String str = "abc";
    }

    /**
     * 前 k 个高频单词
     * @param words
     * @param k
     * @return
     */
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> hash = new HashMap<>();
        for(String word: words) {
            hash.put(word, hash.getOrDefault(word, 0) + 1);
        }
        // 建立小根堆
        PriorityQueue<String> priorityQueue = new PriorityQueue<>((v1, v2) -> {
            if (hash.get(v1) == hash.get(v2)) {
                return v2.compareTo(v1);
            } else {
                return hash.get(v1) - hash.get(v2);
            }
        });
        int count = 0;
        for(String key: hash.keySet()) {
            if (count < k) {
                priorityQueue.add(key);
                count++;
            } else {
                String str = priorityQueue.peek();
                if ((hash.get(key) > hash.get(str) || (hash.get(key) == hash.get(str) && key.compareTo(str) < 0))) {
                    priorityQueue.poll();
                    priorityQueue.add(key);
                }
            }
        }
        List<String> res = new ArrayList<>();
        while(!priorityQueue.isEmpty()) {
            res.add(priorityQueue.poll());
        }
        Collections.reverse(res);
        return res;
    }
}

/**
 * 数据流的中位数
 */
class MedianFinder {
    PriorityQueue<Integer> leftQueue = null; // 左边元素建立大根堆
    PriorityQueue<Integer> rightQueue = null; // 右边元素建立小根堆
    int count = 0;
    public MedianFinder() {
        leftQueue = new PriorityQueue<>((v1, v2) -> {
            return v2 - v1;
        });
        rightQueue =  new PriorityQueue<>((v1, v2) -> {
            return v1 - v2;
        });
        count = 0;
    }

    public void addNum(int num) {
        if (count == 0) {
            leftQueue.add(num);
        } else {
            if (num > leftQueue.peek()) {
                rightQueue.add(num);
            } else {
                leftQueue.add(num);
            }
            // 调整堆
            int leftSize = leftQueue.size();
            int rightSize = rightQueue.size();
            if (leftSize - rightSize >= 2) {
                rightQueue.add(leftQueue.poll());
            } else if (rightSize - leftSize > 0) {
                leftQueue.add(rightQueue.poll());
            }
        }
        count++;
    }

    public double findMedian() {
        if (count % 2 == 0) {
            return ((leftQueue.peek() + rightQueue.peek()) / 2.0);
        } else {
            return (double) leftQueue.peek();
        }
    }
}

  class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {

    }
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Pair<K, V> {
    private K key;
    private V value;

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    // Getters and Setters
    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public void setValue(V value) {
        this.value = value;
    }
}